GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Grover-Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Grover-Algorithmus</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Der Grover-Algorithmus ist ein <a href="Quantenalgorithmus" title="Quantenalgorithmus">Quantenalgorithmus</a> zur Suche in einer un<a href="Sortierung" title="Sortierung">sortierten</a> <a href="Datenbank" title="Datenbank">Datenbank</a> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> Einträgen in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}">

</mrow>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/079224ec761afd92fcb5e336b651f1b2d571cdc3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.366ex; height:3.343ex;" alt="{\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}" loading="lazy"> Schritten und mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}\left(\log N\right)}">

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(\log N\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2d1d068792c8a06a038d467b25d20d3decd20989.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.469ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(\log N\right)}" loading="lazy"> Speicherbedarf (siehe <a href="O-Notation" class="mw-redirect" title="O-Notation">O-Notation</a>). Er wurde von <a href="Lov_Grover" title="Lov Grover">Lov Grover</a> im Jahre <a href="1996" title="1996">1996</a> veröffentlicht<a href="#cite_note-GROVER-1996-1">[1]</a> und gehört zu den ersten Quantenalgorithmen, für die bewiesen wurde, dass sie mit der Problemgröße besser skalieren als der beste klassische Algorithmus. Im Fall des Grover-Algorithmus handelt es sich um einen quadratischen Speedup.

Auf einem klassischen Computer ist der prinzipiell schnellstmögliche Suchalgorithmus in einer unsortierten Datenbank die <a href="Lineare_Suche" title="Lineare Suche">lineare Suche</a>, die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}\left(N\right)}">

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(N\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6b85da32f283eb914f381d9252cea80c3c3d504.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.11ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(N\right)}" loading="lazy"> Rechenschritte erfordert. Der Grover-Algorithmus liefert damit eine quadratische Beschleunigung, was für große <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> beträchtlich ist.

Wie die meisten Quantenalgorithmen ist der Grover-Algorithmus ein <a href="Probabilistischer_Algorithmus" class="mw-redirect" title="Probabilistischer Algorithmus">probabilistischer Algorithmus</a>, d. h., er gibt die korrekte Antwort mit hoher <a href="Wahrscheinlichkeit" title="Wahrscheinlichkeit">Wahrscheinlichkeit</a>, wobei die Wahrscheinlichkeit einer fehlerhaften Antwort durch wiederholte Ausführung des Algorithmus verkleinert werden kann.

<div class="mw-heading mw-heading2"><h2 id="Anwendungen">Anwendungen</h2></div>

Der Grover-Algorithmus ermöglicht eigentlich nicht die direkte Suche in unsortierten Datenbanken, sondern die <a href="Umkehrfunktion" title="Umkehrfunktion">Umkehrung</a> einer endlichen Funktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y=f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=f(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2311a6a75c54b0ea085a381ba472c31d59321514.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.672ex; height:2.843ex;" alt="{\displaystyle y=f(x)}" loading="lazy">, denn zu einem gegebenen Wert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> entspricht ein Wert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=f^{-1}(y)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=f^{-1}(y)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8c259d877499b841cadd9d19146f2413cec1882.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.046ex; height:3.176ex;" alt="{\displaystyle x=f^{-1}(y)}" loading="lazy"> der Suche nach einem Wert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> im <a href="Definitionsbereich" class="mw-redirect" title="Definitionsbereich">Definitionsbereich</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">.

Der Grover-Algorithmus kann ebenso zur Berechnung des <a href="Mittelwert" title="Mittelwert">Mittelwerts</a> und des <a href="Median" title="Median">Medians</a> einer Menge von Zahlen verwendet werden sowie zur Lösung des Kollisionsproblems. Weiter kann er zur Lösung <a href="NP-vollst%C3%A4ndig" class="mw-redirect" title="NP-vollständig">NP-vollständiger</a> Probleme eingesetzt werden, indem er die Menge aller möglichen Probleme durchläuft. Obwohl damit NP-vollständige Probleme beträchtlich schneller gelöst werden können, ermöglicht auch der Grover-Algorithmus keine Lösung in <a href="P_(Komplexit%C3%A4tsklasse)" title="P (Komplexitätsklasse)">polynomialer Zeitkomplexität</a>.

<div class="mw-heading mw-heading2"><h2 id="Detaillierter_Ablauf">Detaillierter Ablauf</h2></div>

Der folgende Ablauf des Algorithmus bezieht sich auf die Suche nach einem einzelnen Sucheintrag. Der Algorithmus kann weiter optimiert werden, um einen von mehreren möglichen Einträgen zu finden, wobei deren Anzahl im Vorfeld bekannt ist.

<div class="mw-heading mw-heading3"><h3 id="Voraussetzungen">Voraussetzungen</h3></div>

Gegeben sei eine unsortierte Datenbank mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> Einträgen, die in einem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">-dimensionalen <a href="Quantenmechanischer_Zustand" class="mw-redirect" title="Quantenmechanischer Zustand">Zustandsraum</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"> durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}N}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ebbb0de63b56848f6d121470d64eb2359472a6e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.477ex; height:2.676ex;" alt="{\displaystyle \log _{2}N}" loading="lazy"> <a href="Qubit" title="Qubit">Qubits</a> dargestellt wird. Die Einträge seien mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0,1,\dots ,(N-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0,1,\dots ,(N-1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b97a047a13853018e4ceadeaac71a52a71228d0e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.413ex; height:2.843ex;" alt="{\displaystyle 0,1,\dots ,(N-1)}" loading="lazy"> durchnummeriert. Dann wählen wir eine auf <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"> wirkende <a href="Observable" title="Observable">Observable</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> verschiedenen <a href="Eigenzustand" title="Eigenzustand">Eigenzuständen</a>

<mrow>

<mrow>

</mrow>

<mrow>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\{\left\vert 0\right\rangle ,\left\vert 1\right\rangle ,\cdots ,\left\vert N-1\right\rangle \right\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d1704da1f8e9854511710fb53cc8d0cc7c2e94a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.357ex; height:2.843ex;" alt="{\displaystyle \left\{\left\vert 0\right\rangle ,\left\vert 1\right\rangle ,\cdots ,\left\vert N-1\right\rangle \right\}}" loading="lazy"></dd></dl>

(in der <a href="Bra-Ket" class="mw-redirect" title="Bra-Ket">Bra-Ket</a>-Notation) und den zugehörigen <a href="Eigenwert" class="mw-redirect" title="Eigenwert">Eigenwerten</a>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\{\lambda _{0},\lambda _{1},\cdots ,\lambda _{N-1}\right\}.}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/191032477c7d57dbc7c6d5d5d1d53998be64081c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.537ex; height:2.843ex;" alt="{\displaystyle \left\{\lambda _{0},\lambda _{1},\cdots ,\lambda _{N-1}\right\}.}" loading="lazy"></dd></dl>

Ferner sei ein <a href="Unit%C3%A4rer_Operator" title="Unitärer Operator">unitärer Operator</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f6ac6ea54ea1b4c9d302cdb049c96d4634e76413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.842ex; height:2.509ex;" alt="{\displaystyle U_{\omega }}" loading="lazy"> gegeben, der eine <a href="Subroutine" class="mw-redirect" title="Subroutine">Subroutine</a>, das sogenannte <a href="Orakel-Turingmaschine" title="Orakel-Turingmaschine">Orakel</a>, darstellt, die die Datenbankeinträge <a href="P_(Komplexit%C3%A4tsklasse)" title="P (Komplexitätsklasse)">effizient</a> nach dem Suchkriterium vergleicht. Der Algorithmus legt nicht fest, wie das Orakel arbeitet, es muss allerdings die <a href="Superposition_(Physik)" title="Superposition (Physik)">Superposition</a> der Quantenzustände verarbeiten und den gesuchten Eigenzustand <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert \omega \right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/077899ea8f917bac3c660bc7e2376ff5f71dff35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle \left\vert \omega \right\rangle }" loading="lazy"> erkennen:

<msub>

</mrow>

</msub>

<mrow>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }\left\vert \omega \right\rangle =-\left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/238fce50b310db800321e3049a60b70355b6a333.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.517ex; height:2.843ex;" alt="{\displaystyle U_{\omega }\left\vert \omega \right\rangle =-\left\vert \omega \right\rangle }" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }\left\vert x\right\rangle =\left\vert x\right\rangle \qquad \forall x\neq \omega }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1700ab1f8e8294af9ac2c6464a817195712438c4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.289ex; height:2.843ex;" alt="{\displaystyle U_{\omega }\left\vert x\right\rangle =\left\vert x\right\rangle \qquad \forall x\neq \omega }" loading="lazy"></dd></dl>

Ziel des Algorithmus ist es, diesen Eigenzustand <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert \omega \right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/077899ea8f917bac3c660bc7e2376ff5f71dff35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle \left\vert \omega \right\rangle }" loading="lazy">, bzw. äquivalent den Eigenwert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{\omega }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/030fd922b32e729cf848727df5b53b1c67853874.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.61ex; height:2.509ex;" alt="{\displaystyle \lambda _{\omega }}" loading="lazy"> zu identifizieren.

<div class="mw-heading mw-heading3"><h3 id="Schrittabfolge">Schrittabfolge</h3></div>

<ol><li>Initialisiere das System in den Zustand

<mrow>

</mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mrow>

</munder>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert s\right\rangle ={\frac {1}{\sqrt {N}}}\sum _{x}\left\vert x\right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c65ae90e10c88d703cec6e4c14437b95a57b997c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:17.586ex; height:6.343ex;" alt="{\displaystyle \left\vert s\right\rangle ={\frac {1}{\sqrt {N}}}\sum _{x}\left\vert x\right\rangle }" loading="lazy"></dd></dl></li>

<li>Führe die folgende sog. Grover-Iteration <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r(N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r(N)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c9ac6097c5943a4ae5d12f95478b55a2acc93b7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.922ex; height:2.843ex;" alt="{\displaystyle r(N)}" loading="lazy">-mal durch. (Die Funktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> wird weiter unten beschrieben.)

<ol><li>Wende den Operator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{\omega }=I-2\left\vert \omega \right\rangle \left\langle \omega \right\vert }">

<msub>

</mrow>

</msub>

<mrow>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }=I-2\left\vert \omega \right\rangle \left\langle \omega \right\vert }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bd2c5dc972525e26519fe0eb07eaa1f44d68a2ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.884ex; height:2.843ex;" alt="{\displaystyle U_{\omega }=I-2\left\vert \omega \right\rangle \left\langle \omega \right\vert }" loading="lazy"> an (erste <a href="Householdertransformation" title="Householdertransformation">Householdertransformation</a>).</li>

<li>Wende den Operator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{s}=-(I-2\left\vert s\right\rangle \left\langle s\right\vert )}">

<msub>

</mrow>

</msub>

<mrow>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}=-(I-2\left\vert s\right\rangle \left\langle s\right\vert )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c010d959c4f0ba27d131a768df4a37e67b4bbc67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.539ex; height:2.843ex;" alt="{\displaystyle U_{s}=-(I-2\left\vert s\right\rangle \left\langle s\right\vert )}" loading="lazy"> an (zweite <a href="Householdertransformation" title="Householdertransformation">Householdertransformation</a>).</li></ol></li>

<li>Führe die <a href="Observable" title="Observable">Messung</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy"> durch. Das <a href="Messergebnis" title="Messergebnis">Messergebnis</a> beträgt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{\omega }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/030fd922b32e729cf848727df5b53b1c67853874.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.61ex; height:2.509ex;" alt="{\displaystyle \lambda _{\omega }}" loading="lazy"> mit einer Wahrscheinlichkeit nahe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\gg 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\gg 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b7067e3506c2342958dfbe0058ae7563915b852c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.84ex; height:2.176ex;" alt="{\displaystyle N\gg 1}" loading="lazy">. Mit der Messung von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{\omega }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/030fd922b32e729cf848727df5b53b1c67853874.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.61ex; height:2.509ex;" alt="{\displaystyle \lambda _{\omega }}" loading="lazy"> ist das System im Zustand <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/48eff443f9de7a985bb94ca3bde20813ea737be8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.446ex; height:1.676ex;" alt="{\displaystyle \omega }" loading="lazy">.</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Geometrische_Sicht_und_Bestimmung_der_Schrittzahl_r(N)">Geometrische Sicht und Bestimmung der Schrittzahl r(N)</h2></div>

Der Anfangszustand lautet

</mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mrow>

</munder>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x}|x\rangle .}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/78bc7a73c7120b97ed8ef7ea4005c7d012a6fecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:18.233ex; height:6.343ex;" alt="{\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x}|x\rangle .}" loading="lazy"></dd></dl>

Betrachten wir die von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert s\right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert s\right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2da65c064bd93db44d766fba74d1252127bb4a21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.642ex; height:2.843ex;" alt="{\displaystyle \left\vert s\right\rangle }" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert \omega \right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/077899ea8f917bac3c660bc7e2376ff5f71dff35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle \left\vert \omega \right\rangle }" loading="lazy"> aufgespannte Ebene. Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \vert \omega ^{\times }\rangle }">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vert \omega ^{\times }\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9dd910258fcc7deed3ea704a651c66571771f15b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.508ex; height:2.843ex;" alt="{\displaystyle \vert \omega ^{\times }\rangle }" loading="lazy"> ein Ket-Vektor in dieser Ebene, senkrecht zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert \omega \right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/077899ea8f917bac3c660bc7e2376ff5f71dff35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle \left\vert \omega \right\rangle }" loading="lazy">. Da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert \omega \right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/077899ea8f917bac3c660bc7e2376ff5f71dff35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle \left\vert \omega \right\rangle }" loading="lazy"> einer der Basisvektoren ist, folgt

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle \omega \mid s\rangle ={\frac {1}{\sqrt {N}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fbc875964a6a73383601395d1ca1a366ff4f786e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:14.217ex; height:6.176ex;" alt="{\displaystyle \langle \omega \mid s\rangle ={\frac {1}{\sqrt {N}}}}" loading="lazy"></dd></dl>

Geometrisch bedeutet das, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert \omega \right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/077899ea8f917bac3c660bc7e2376ff5f71dff35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle \left\vert \omega \right\rangle }" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert s\right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert s\right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2da65c064bd93db44d766fba74d1252127bb4a21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.642ex; height:2.843ex;" alt="{\displaystyle \left\vert s\right\rangle }" loading="lazy"> in einem Winkel von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {\pi }{2}}-\theta }">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {\pi }{2}}-\theta }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e626e6f6baf786093789553eab36d6d40335262e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:5.709ex; height:3.176ex;" alt="{\displaystyle {\tfrac {\pi }{2}}-\theta }" loading="lazy"> zueinander stehen, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta =\theta (N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta =\theta (N)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b11a510f7ec3999e2930942917c066f2ead43e11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.152ex; height:2.843ex;" alt="{\displaystyle \theta =\theta (N)}" loading="lazy"> gegeben ist durch

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \cos \left({\frac {\pi }{2}}-\theta \right)={\frac {1}{\sqrt {N}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86bb292b470407bea4da98b2b1bd73ab75a4f8bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:19.92ex; height:6.176ex;" alt="{\displaystyle \cos \left({\frac {\pi }{2}}-\theta \right)={\frac {1}{\sqrt {N}}}}" loading="lazy"></dd></dl>

folglich ist

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sin \theta ={\frac {1}{\sqrt {N}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/680f4605e9b7c19db9b52aff25e0e31cd88adc2e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:12.267ex; height:6.176ex;" alt="{\displaystyle \sin \theta ={\frac {1}{\sqrt {N}}}}" loading="lazy"></dd></dl>

Der Operator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f6ac6ea54ea1b4c9d302cdb049c96d4634e76413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.842ex; height:2.509ex;" alt="{\displaystyle U_{\omega }}" loading="lazy"> ist eine <a href="Spiegelung_(Geometrie)#Spiegelungen_in_Räumen_beliebiger_Dimension" title="Spiegelung (Geometrie)">Spiegelung</a> an der zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert \omega \right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/077899ea8f917bac3c660bc7e2376ff5f71dff35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle \left\vert \omega \right\rangle }" loading="lazy"> orthogonalen <a href="Hyperebene" title="Hyperebene">Hyperebene</a>; für Vektoren in der von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert s\right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert s\right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2da65c064bd93db44d766fba74d1252127bb4a21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.642ex; height:2.843ex;" alt="{\displaystyle \left\vert s\right\rangle }" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert \omega \right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/077899ea8f917bac3c660bc7e2376ff5f71dff35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle \left\vert \omega \right\rangle }" loading="lazy"> aufgespannten Ebene wirkt er als Spiegelung an der Geraden durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \vert \omega ^{\times }\rangle }">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vert \omega ^{\times }\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9dd910258fcc7deed3ea704a651c66571771f15b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.508ex; height:2.843ex;" alt="{\displaystyle \vert \omega ^{\times }\rangle }" loading="lazy">. Der Operator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{s}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e61d1a3cbea2c02997c2a9416a0bd82fed911f75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.591ex; height:2.509ex;" alt="{\displaystyle U_{s}}" loading="lazy"> ist eine Spiegelung an der Geraden durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert s\right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert s\right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2da65c064bd93db44d766fba74d1252127bb4a21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.642ex; height:2.843ex;" alt="{\displaystyle \left\vert s\right\rangle }" loading="lazy">. Der Zustandsvektor bleibt also nach der Anwendung von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{s}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e61d1a3cbea2c02997c2a9416a0bd82fed911f75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.591ex; height:2.509ex;" alt="{\displaystyle U_{s}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f6ac6ea54ea1b4c9d302cdb049c96d4634e76413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.842ex; height:2.509ex;" alt="{\displaystyle U_{\omega }}" loading="lazy"> in der durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert s\right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert s\right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2da65c064bd93db44d766fba74d1252127bb4a21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.642ex; height:2.843ex;" alt="{\displaystyle \left\vert s\right\rangle }" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert \omega \right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/077899ea8f917bac3c660bc7e2376ff5f71dff35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle \left\vert \omega \right\rangle }" loading="lazy"> aufgespannten Ebene. Damit rotiert der Operator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{s}\ U_{\omega }}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}\ U_{\omega }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bac815c8963b8af5ce8e6269d77546877a539396.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.014ex; height:2.509ex;" alt="{\displaystyle U_{s}\ U_{\omega }}" loading="lazy"> bei jedem Schritt der Grover-Iteration den Zustandsvektor um einen Winkel von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\theta }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/493f1772ffdb7096362a9de2d587b65a79f4b6f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.253ex; height:2.176ex;" alt="{\displaystyle 2\theta }" loading="lazy"> nach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert \omega \right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/077899ea8f917bac3c660bc7e2376ff5f71dff35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle \left\vert \omega \right\rangle }" loading="lazy">.

Der Algorithmus muss also anhalten, sobald der Zustandsvektor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert \omega \right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/077899ea8f917bac3c660bc7e2376ff5f71dff35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle \left\vert \omega \right\rangle }" loading="lazy"> am nächsten gekommen ist. Weitere Iterationen würden ihn wieder davon weg drehen und damit die Wahrscheinlichkeit der korrekten Antwort wieder verkleinern. Für die optimale Anzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> an Iterationen zur exakten Übereinstimmung mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert \omega \right\rangle }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert \omega \right\rangle }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/077899ea8f917bac3c660bc7e2376ff5f71dff35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle \left\vert \omega \right\rangle }" loading="lazy"> gilt

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {\pi }{2}}-\theta =2\theta r,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/17bcd9c273a9acc4377f36a5f880b5bf371ed6fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:13.146ex; height:4.676ex;" alt="{\displaystyle {\frac {\pi }{2}}-\theta =2\theta r,}" loading="lazy"></dd></dl>

also

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r(N)={\frac {\pi }{4\theta (N)}}-{\frac {1}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3b804050808d3ae252e1f18fcab7444dbec34ede.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:19.821ex; height:6.009ex;" alt="{\displaystyle r(N)={\frac {\pi }{4\theta (N)}}-{\frac {1}{2}}}" loading="lazy"></dd></dl>

Da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> aber eine <a href="Ganze_Zahl" title="Ganze Zahl">ganze Zahl</a> sein muss, setzen wir <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> gleich der gerundeten Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {\pi }{4\theta }}-{\tfrac {1}{2}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {\pi }{4\theta }}-{\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86e3b0dec9af99758636c89e55f6f9716f047cac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:6.928ex; height:3.676ex;" alt="{\displaystyle {\tfrac {\pi }{4\theta }}-{\tfrac {1}{2}}}" loading="lazy">. Damit beträgt die Wahrscheinlichkeit, eine falsche Antwort zu messen, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}\left(1-\cos ^{2}\theta \right)={\mathcal {O}}\left(\sin ^{2}\theta \right)}">

</mrow>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(1-\cos ^{2}\theta \right)={\mathcal {O}}\left(\sin ^{2}\theta \right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9692317739db36dfcf7d7a08edf9cc182c53c2c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:26.865ex; height:3.343ex;" alt="{\displaystyle {\mathcal {O}}\left(1-\cos ^{2}\theta \right)={\mathcal {O}}\left(\sin ^{2}\theta \right)}" loading="lazy">. Die Irrtumswahrscheinlichkeit bei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> Datenbankeinträgen lautet also asymptotisch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}\left({\tfrac {1}{N}}\right)}">

</mrow>

<mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left({\tfrac {1}{N}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65383e6108273a90565b323bcff1e1a3cdee1839.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:7.308ex; height:4.843ex;" alt="{\displaystyle {\mathcal {O}}\left({\tfrac {1}{N}}\right)}" loading="lazy">, d. h., sie ist vernachlässigbar klein für große <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">.

Für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\gg 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\gg 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b7067e3506c2342958dfbe0058ae7563915b852c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.84ex; height:2.176ex;" alt="{\displaystyle N\gg 1}" loading="lazy"> gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta \approx N^{-{\frac {1}{2}}}}">

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta \approx N^{-{\frac {1}{2}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c9c67aac95b335c9cc396ca5d606dff9adbf9c70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.326ex; height:3.509ex;" alt="{\displaystyle \theta \approx N^{-{\frac {1}{2}}}}" loading="lazy">, also

<mfrac>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r(N)\longrightarrow {\frac {\pi {\sqrt {N}}}{4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3bffc84aad48810b8a714cb5eace9c86f61e69f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:16.185ex; height:5.843ex;" alt="{\displaystyle r(N)\longrightarrow {\frac {\pi {\sqrt {N}}}{4}}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Erweiterungen">Erweiterungen</h2></div>

Enthält die Datenbank nicht nur einen, sondern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> gesuchte Einträge, so funktioniert der Algorithmus ebenfalls, allerdings gilt für die Anzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> durchzuführender Iterationen nun <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{k}}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

<msqrt>

<mfrac>

</mfrac>

</mstyle>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{k}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/20f2470413e57529f064f49fc6c7e3c18613693b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.397ex; height:4.843ex;" alt="{\displaystyle {\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{k}}}}" loading="lazy"> statt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {\pi }{4}}{\sqrt {N}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {\pi }{4}}{\sqrt {N}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dd250231d4f7f59f13aab3fde183bc613fa82eb5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:5.778ex; height:3.509ex;" alt="{\displaystyle {\tfrac {\pi }{4}}{\sqrt {N}}}" loading="lazy">.

Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> unbekannt, so führt man den Grover-Algorithmus in

<mfrac>

</mfrac>

</mstyle>

</mrow>

<msqrt>

<mfrac>

</mfrac>

</mstyle>

</msqrt>

</mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

<msqrt>

<mfrac>

</mfrac>

</mstyle>

</msqrt>

</mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

<msqrt>

<mfrac>

</mfrac>

</mstyle>

</msqrt>

</mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

<msqrt>

<mfrac>

</mfrac>

</mstyle>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{1}}},\;{\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{2}}},\;{\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{4}}},\;{\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{8}}},\ldots }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9165390928a28b5d3f90b0c21865826c787ca88a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:34.383ex; height:4.843ex;" alt="{\displaystyle {\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{1}}},\;{\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{2}}},\;{\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{4}}},\;{\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{8}}},\ldots }" loading="lazy"></dd></dl>

Iterationen durch. Für beliebiges <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> wird ein gesuchter Eintrag mit genügend hoher Wahrscheinlichkeit gefunden. Die Gesamtzahl von Iterationen beträgt höchstens

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

<mrow>

<mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi {\frac {\sqrt {N}}{4}}\left(1+{\frac {1}{\sqrt {2}}}+{\frac {1}{2}}+\cdots \right)={\mathcal {O}}\left({\sqrt {N}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/411beccca7bea29c67f7a24e011b58b9328829b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:39.781ex; height:6.843ex;" alt="{\displaystyle \pi {\frac {\sqrt {N}}{4}}\left(1+{\frac {1}{\sqrt {2}}}+{\frac {1}{2}}+\cdots \right)={\mathcal {O}}\left({\sqrt {N}}\right)}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Optimalität_des_Grover-Algorithmus">Optimalität des Grover-Algorithmus</h2></div>

Der Grover-Algorithmus ist optimal in dem Sinne, dass es keinen Quantenalgorithmus mit weniger als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}">

</mrow>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/079224ec761afd92fcb5e336b651f1b2d571cdc3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.366ex; height:3.343ex;" alt="{\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}" loading="lazy"> Rechenschritten geben kann.<a href="#cite_note-BENNETT-ET-AL-2">[2]</a> Dieses Resultat ist wichtig, um die Grenzen des Quantenrechnens zu verstehen.

Wäre das <a href="Suchproblem" title="Suchproblem">Suchproblem</a> beispielsweise mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}\left(\log ^{c}N\right)}">

</mrow>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(\log ^{c}N\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1ee9544a71369c1cec56606a2b0806cc6e3c49bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(\log ^{c}N\right)}" loading="lazy"> Schritten lösbar, so wäre <a href="NP_(Komplexit%C3%A4tsklasse)" title="NP (Komplexitätsklasse)">NP</a> in <a href="BQP" title="BQP">BQP</a> enthalten.

Ebenso ist die Anzahl i. A. notwendiger Iterationen für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> gesuchte Einträge, also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi {\sqrt {\tfrac {N}{2k}}}}">

<msqrt>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi {\sqrt {\tfrac {N}{2k}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b73a5c9760e564b078f5d0bf46587d33cd35a9b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.17ex; height:4.843ex;" alt="{\displaystyle \pi {\sqrt {\tfrac {N}{2k}}}}" loading="lazy">, optimal.

<div class="mw-heading mw-heading2"><h2 id="Qualitatives_Argument">Qualitatives Argument</h2></div>

Um ein <a href="Heuristik" title="Heuristik">heuristisches</a> Verständnis des quantenmechanischen Verfahrens im Vergleich zum klassischen Vorgehen zu gewinnen, und für Verallgemeinerungen, ist es sinnvoll den folgenden Spezialfall zu betrachten: die gesuchte Information soll auf einem spezifischen Gitterpunkt eines Quadratgitters liegen. Die Suche erfordert also klassisch im schlimmsten Fall <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> Schritte, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {N}}}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {N}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7b3d8948b2c154ccc7f7523b035ae7e254e04190.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.999ex; height:3.009ex;" alt="{\displaystyle {\sqrt {N}}}" loading="lazy"> die Kantenlänge des Quadrates ist. Quantenmechanische Zustände sind dagegen Strahlen im <a href="Hilbertraum" title="Hilbertraum">Hilbertraum</a>, d. h., sie sind nur bis auf einen Faktor bestimmt, und wenn man vom Zentrum des Quadrates ausgeht, ist die Richtung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> des Strahls durch eine Punktmenge gegeben, welche nur dem Umfang und nicht dem Inhalt des Quadrates entspricht, also einer Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sim {\mathcal {O}}\!\left({\sqrt {N}}\right)}">

</mrow>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sim {\mathcal {O}}\!\left({\sqrt {N}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a38fbf69333331cb3ff31511a697baf080171403.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.433ex; height:3.343ex;" alt="{\displaystyle \sim {\mathcal {O}}\!\left({\sqrt {N}}\right)}" loading="lazy">. Um einen speziellen Punkt auf dem gewählten Strahl zu finden, muss man nur noch Interferenzexperimente mit anderen quantenmechanischen Zuständen durchführen, was praktisch ohne zusätzlichen Zeitaufwand möglich ist. Die gesuchte Information erhält man also quantenmechanisch in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}\!\left({\sqrt {N}}\right)}">

</mrow>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\!\left({\sqrt {N}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/712d5add2e74ac92e7efbe294085b650a623ebb1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.979ex; height:3.343ex;" alt="{\displaystyle {\mathcal {O}}\!\left({\sqrt {N}}\right)}" loading="lazy"> Schritten.

<div class="mw-heading mw-heading2"><h2 id="Verwandte_Themen">Verwandte Themen</h2></div>

Ein ganz anderes Problem, bei dem <a href="Quantencomputer" title="Quantencomputer">Quantencomputer</a> ebenfalls eine wesentliche Beschleunigung bringen, betrifft die Faktorisierung einer sehr großen Zahl (siehe <a href="Shor-Algorithmus" title="Shor-Algorithmus">Shor-Algorithmus</a>).

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>M. Homeister: Quantum Computing verstehen Springer Vieweg, Wiesbaden 2018, fünfte Auflage, ISBN 978-3-6582-2883-5, S. 137ff.</li>

<li>B. Lenze: Mathematik und Quantum Computing Logos Verlag, Berlin 2020, zweite Auflage, ISBN 978-3-8325-4716-5, S. 57ff.</li>

<li><a href="Richard_J._Lipton" title="Richard J. Lipton">R. J. Lipton</a>, K. W. Regan: Quantum Algorithms via Linear Algebra: A Primer MIT Press, Cambridge MA 2014, ISBN 978-0-2620-2839-4, S. 115ff.</li>

<li><a href="Michael_Nielsen" title="Michael Nielsen">M. A. Nielsen</a>, <a href="Isaac_Chuang" title="Isaac Chuang">I. L. Chuang</a>: <cite style="font-style:italic">Quantum Computation and Quantum Information.</cite> Cambridge University Press, Cambridge MA 2010, ISBN 978-1-107-00217-3, S. 248 ff. (<a rel="nofollow" class="external text" href="https://profmcruz.files.wordpress.com/2017/08/quantum-computation-and-quantum-information-nielsen-chuang.pdf">wordpress.com</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Grover-Algorithmus&rft.au=M.+A.+Nielsen%2C+I.+L.+Chuang&rft.btitle=Quantum+Computation+and+Quantum+Information.&rft.date=2010&rft.genre=book&rft.isbn=9781107002173&rft.pages=248ff.&rft.place=Cambridge+MA&rft.pub=Cambridge+University+Press" style="display:none"> </li>

<li>W. Scherer: Mathematik der Quanteninformatik Springer-Verlag, Berlin-Heidelberg 2016, ISBN 978-3-6624-9079-2, S. 235ff.</li>

<li>C. P. Williams: Explorations in Quantum Computing Springer-Verlag, London 2011, zweite Auflage, ISBN 978-1-8462-8886-9, S. 245ff.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li>L. K. Grover: <a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0109116">From Schrödinger's equation to quantum search algorithm</a>, American Journal of Physics, 69(7): 769-777, 2001. Überblick über den Algorithmus und seine Geschichte (englisch)</li>

<li>L. K. Grover: <a rel="nofollow" class="external text" href="https://cryptome.org/qc-grover.htm">Quantum Computing: How the weird logic of the subatomic world could make it possible for machines to calculate millions of times faster than they do today</a>, In: The Sciences, July/August 1999, S. 24–30. (englisch)</li>

/* start https://de.wikipedia.org/ */

.mw-parser-output .webarchiv-memento a{color:inherit}

/* end https://de.wikipedia.org/ */

</style><a rel="nofollow" class="external text" href="https://web.archive.org/web/20140201230754/http://www.bell-labs.com/user/feature/archives/lkgrover/">What's a Quantum Phone Book?</a> (<a href="Webarchivierung#Begrifflichkeiten" title="Webarchivierung">Memento</a> vom 1. Februar 2014 im <a href="Internet_Archive" title="Internet Archive">Internet Archive</a>), Lov Grover, Bell Labs</li>

<li>J. Marre: <a rel="nofollow" class="external text" href="https://www.quantencomputer-info.de/quantencomputer/grover-algorithmus/">Der Grover-Algorithmus und die Suche nach dem heiligen Gral</a> In: quantencomputer-info veröffentlicht 11. September 2018</li>

<li>Quanten-Suchalgorithmus In: Norbert Linke, Markus Müller: <cite style="font-style:italic">Quantencomputer auf Basis von Ionen in Fallen. Mit Ionen ist zu rechnen</cite>. In: <cite style="font-style:italic"><a href="Physik_in_unserer_Zeit" title="Physik in unserer Zeit">Physik in unserer Zeit</a></cite>. 2020, S. 162–173 (<a rel="nofollow" class="external text" href="https://onlinelibrary.wiley.com/doi/pdf/10.1002/piuz.202001571">wiley.com</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Grover-Algorithmus&rft.atitle=Quantencomputer+auf+Basis+von+Ionen+in+Fallen.+Mit+Ionen+ist+zu+rechnen&rft.au=Norbert+Linke%2C+Markus+M%C3%BCller&rft.btitle=Physik+in+unserer+Zeit&rft.date=2020&rft.genre=book&rft.pages=162-173" style="display:none"> </li>

<li>Reinhard Karnapke, Simon Rieche: Grover-Algorithmus In: <a rel="nofollow" class="external text" href="http://page.mi.fu-berlin.de/alt/vorlesungen/sem02/rieche-zsf.pdf">Quantensuchalgorithmen</a> S. 3–7 Seminarunterlagen Sommersemester 2002</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-GROVER-1996-1"><a href="#cite_ref-GROVER-1996_1-0">↑</a> <a href="Lov_Grover" title="Lov Grover">L. K. Grover</a>: <cite style="font-style:italic">A fast quantum mechanical algorithm for database search</cite>. In: <cite style="font-style:italic">Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC)</cite>. Mai 1996, S. 212–219, <a href="ArXiv" title="ArXiv">arxiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9605043">quant-ph/9605043</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Grover-Algorithmus&rft.atitle=A+fast+quantum+mechanical+algorithm+for+database+search&rft.au=L.+K.+Grover&rft.btitle=Proceedings%2C+28th+Annual+ACM+Symposium+on+the+Theory+of+Computing+%28STOC%29&rft.date=1996-05&rft.genre=book&rft.pages=212-219" style="display:none">

</li>

<li id="cite_note-BENNETT-ET-AL-2"><a href="#cite_ref-BENNETT-ET-AL_2-0">↑</a> <a href="Charles_H._Bennett_(Physiker)" title="Charles H. Bennett (Physiker)">C. H. Bennett</a>, <a href="Gilles_Brassard" title="Gilles Brassard">G. Brassard</a>, <a href="Umesh_Vazirani" title="Umesh Vazirani">Vazirani U.</a>: <cite style="font-style:italic">The strengths and weaknesses of quantum computation</cite>. In: <cite style="font-style:italic">SIAM Journal on Computing</cite>. Band 26, Nr. 5, 1997, S. 1510–1523, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137/s0097539796300933">10.1137/s0097539796300933</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Grover-Algorithmus&rft.atitle=The+strengths+and+weaknesses+of+quantum+computation&rft.au=C.+H.+Bennett%2C++G.+Brassard%2C+Vazirani+U.&rft.date=1997&rft.doi=10.1137%2Fs0097539796300933&rft.genre=journal&rft.issue=5&rft.jtitle=SIAM+Journal+on+Computing&rft.pages=1510-1523&rft.volume=26" style="display:none">

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-11-13" href="https://de.wikipedia.org/wiki/?title=Grover-Algorithmus&oldid=250301720">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>